// HJ28 素数伴侣
// https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e
// 困难，HungarianAlgorithm(匈牙利算法
// 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。
// 现在密码学会请你设计一个程序，从已有的 N （ N
// 为偶数）个正整数中挑选出若干对组成“素数伴侣”，
// 挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，
// 而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，
// 当然密码学会希望你寻找出“最佳方案”。
// 输入:一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
// 输出:一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
// 数据范围： 1 \le n \le 100 \1≤n≤100  ，输入的数据大小满足 2 \le val \le 30000
// \2≤val≤30000 1 输入一个正偶数 n 2 输入 n 个整数 输出描述：
// 求得的“最佳方案”组成“素数伴侣”的对数。
// 输入：4
// 2 5 6 13
// 输出：2
// 输入：2
// 3 6
// 输出：0

#include <iostream>
#include <list>
#include <vector>
using namespace std;

bool isPrime(size_t n) {
  for (size_t i = 2; i * i <= n; ++i) {
      if (n % i == 0)
          return false;
  }
  return true;
}

class HungarianAlgorithm {
 private:
  list<pair<size_t, size_t> > pairlist;
  bool matchEven(const vector<vector<bool> >& vtPrimeTbl, vector<bool>& vtVisit,
                 vector<int>& vtMatch, size_t iOdd, size_t nEvenCnt) {
    for (size_t iEven = 0; iEven < nEvenCnt; iEven++)
      if (vtPrimeTbl[iOdd][iEven] && !vtVisit[iEven]) {
        vtVisit[iEven] = true;
        if ( vtMatch[iEven] == -1
             || matchEven(vtPrimeTbl, vtVisit, vtMatch, vtMatch[iEven], nEvenCnt)) {
          vtMatch[iEven] = iOdd;
          vtVisit[iEven] = false;
          return true;
        }
      }
    return false;
  }
 public:
  template <class type>
  HungarianAlgorithm(type const& isPair, size_t nOddCnt, size_t nEvenCnt) {
    if (nOddCnt && nEvenCnt) {
      vector<vector<bool>> vtPrimeTbl(nOddCnt, vector<bool>(nEvenCnt, false));
      vector<int> vtMatch(nEvenCnt, -1);      // match[even] = odd
      vector<bool> vtVisit(nEvenCnt, false);  // visit[even] = false
      for (size_t i = 0; i < nOddCnt; ++i) {
          for (size_t j = 0; j < nEvenCnt; ++j) {
              vtPrimeTbl[i][j] = isPair(i, j);
          }
      }
      for (size_t i = 0; i < nOddCnt; ++i){
          matchEven(vtPrimeTbl, vtVisit, vtMatch, i, nEvenCnt);
      }
      for (size_t j = 0; j < nEvenCnt; ++j) {
          if (vtMatch[j] != -1) {
               pairlist.emplace_back(vtMatch[j], j);
          }
      }
    }
  }
  list<pair<size_t, size_t> > const& getmatch() const {
      return pairlist;
  }
};


int main_primer(void) {
  size_t nCount;
  size_t data;
  while (cin >> nCount) {
    vector<size_t> vtOdd;
    vector<size_t> vtEven;
    for (size_t i = 0; i < nCount; ++i) {
      cin >> data;
      (data%2)? vtOdd.push_back(data) : vtEven.push_back(data);
    }
    auto isPair = [&](size_t i, size_t j) { return isPrime(vtOdd[i] + vtEven[j]); };
    auto res = HungarianAlgorithm(isPair, vtOdd.size(), vtEven.size()).getmatch().size();
    cout << res << endl;
  }
  return 0;
}
